class Solution {
public:
    unordered_map<long long,int> hash;
    
    int integerReplacement(int n) {
        //n的范围太大，不适合vector dp，可以用hash dp
        return dfs(n);//dfs（n）返回n的最小替换次数
    }
    int dfs(long long n)
    {
        if(n==1)
        {
            return 0;
        }
        if(n%2==0)
        {
            hash[n/2]=dfs(n/2);
            return 1+hash[n/2];
        }
        else
        {
            hash[n+1]=dfs(n+1),hash[n-1]=dfs(n-1);
            return 1+min(hash[n-1],hash[n+1]);
        }
    }
};